COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	∂16-Mar-79  1920	PRATT at MIT-AI (Vaughan Pratt)    
C00033 ENDMK
C⊗;
∂16-Mar-79  1920	PRATT at MIT-AI (Vaughan Pratt)    
Date: 16 MAR 1979 2047-EST
From: PRATT at MIT-AI (Vaughan Pratt)
To: jra at SU-AI

In case you can use it, here is a revised version, with 3025 words.



			 LISP - A Mathematician's View

				 Vaughan Pratt
				    M.I.T.


	All higher order languages offer the programmer mechanisms for
simplifying and clarifying programs.  Viewed from the distance that
mathematicians such as myself prefer, away from the distractions of detail,
Lisp stands out as the first language to pay serious attention to the following
issues.

	Mobility of data.
	Modularity of function.
	Declarative programming.
	Metalinguistics (the ability of a language to talk about language).

	Since the development of Lisp two other languages, APL and (to a lesser
extent) Snobol, have joined Lisp in dealing with at least some of these issues.
As such one would assume that they would have improved on Lisp.  We argue that
Lisp outclasses these languages despite its having been developed earlier.
Other languages such as Fortran, Basic, Algol, PL/I, and Pascal (or FBAPP as
Professor Alan Perlis of Yale University refers to them collectively) are in
Perlis's opinion and mine not in the same class as Lisp and APL with respect to
the issues discussed here.  (I do not know Alan's opinion of Snobol.)

1.  Mobility of data

	In a computer, data flows between three major classes of sites:
storage, functions, and devices.  Storage consists of registers and main memory
in assembly language, variables (simple and subscripted) in higher level
languages.  Functions (or procedures, or subroutines) are pretty much the same
in all languages, to within minor technical distinctions.  Typical devices are
printers, keyboards, floppies, paper tape readers, and the like.

	The corresponding mechanisms available to the programmer for expediting
this flow of data are fetch and store instructions, parameter-passing and
value-returning constructs, and read and write commands.  A mobile datum is one
which can be moved from one to site to another by the program with a minimum of
fuss.

	To tell if a data type is mobile, apply the following two tests. 

	The width test.  Must the data be moved piecemeal?  For example, on
your micro, can you move a two-byte address around as a unit, or do you have to
move each byte separately?  In your favorite language, can you read in an
array from floppy disk or paper tape using one instruction, or must you write a
loop to read the array elements individually?

	The length test.  Are intermediate sites needed to get data from one
site to another?  For example, to take the log of a number that the user types
in from a keyboard, do you have to store the number in a variable first and
then take its log, or can you just say (Log (Read)) as in Lisp?

	If the data type fails either test it is not fully mobile.  Note that
if it fails both, the effect can be multiplicative.  Moving say 3 bytes each
requiring 2 steps requires 6 steps altogether.

	One basis for classifying languages is the mobility of their data
types.  On microcomputers only bytes (and sometimes words) are mobile, and even
then often not for I/O.  Only numbers and Booleans, and sometimes strings, are
truly mobile in Basic, Fortran, and Algol.

	The major languages developed in the 50's and 60's whose structured
data types are mobile are (in order of development) Lisp, APL, and Snobol, the
respective types being lists, arrays, and strings.  Lisp and APL also have
mobile strings.  In Lisp atoms serve as strings.  In APL a vector of characters
is printed without spaces between its characters and so can play the role of a
string.  Lisp and Snobol have arrays that are not nearly as mobile as APL's,
though some implementations of Lisp come close, namely to within the ability to
read and write them from and to devices.

	In my opinion lists are preferable to arrays as a general-purpose data
type since anything that an array can represent can be conveniently represented
by a list, whereas the converse is far from true.  You can't have arrays of
differently shaped arrays in APL, for example; Lisp on the other hand permits
any data type to be a list element.  In this respect APL data types are not
fully mobile with respect to array elements viewed as data sites (which they
are).

	From the implementation (and hence efficiency) viewpoint, arrays offer
faster random access.  However, the modern APL style of programming makes
relatively light use of random access.  (This by the way is a potential source
of endless and quite technical debate between Lisp and APL enthusiasts, and is
not by any means an easy issue to dispose of.)  Moreover, as compiler
optimizers get progressively "smarter," it will become progressively harder to
infer properties of the implementation from properties of the language
definition.

	For example, often the compiler has enough information to infer that a
Lisp list is being used array-style, and it can then choose to represent the
list as an array.  Conversely it may spot that an APL array would best be
implemented as a Lisp-style list, e.g. when much concatenation of APL arrays is
being performed and no random access is used.

	An aspect of APL not shared with Lisp is its insistence on homogeneous
arrays.  In APL you can have arrays of numbers, or arrays of characters, but
not arrays of a mixture.  An advantage of this is that you don't need to store
type information for every array element, leading to efficiency gains.  A
disadvantage is that it restricts the programmer's options considerably.  Lisp
programmers take full advantage of the ability to mix types in lists.

	Lisp and APL (and to an extent Snobol) have mobile expressions.  In
Lisp you can treat the expression (Plus x (Times y 5)) as an ordinary datum. 
It can be bound (that is, assigned) to variables, passed as an argument to a
function, returned as the value of the function, printed out, and read back in
a year later still meaning the same thing.  And of course it can be evaluated,
by applying the Lisp function Eval to it.

	The mobility of an expression is inherited from that of its
representing medium, just as the mobility of an integer in the range -128 to
127 is inherited from the mobility of the eight-bit byte that represents it.

	With some restrictions, the same is true of APL.  The string (character
vector) 'X+Yx5' can be passed around just as freely in APL, and of course it
can be executed by applying the APL function Execute to it.  One restriction is
that Execute cannot handle more than one line at a time, effectively preventing
the use of APL's version of Goto in conjunction with Execute.  Another
restriction is that there is no APL expression whose Execution results in an
APL function becoming defined; instead one uses a separate function, quadFX.
Lisp observes neither of these restrictions.

	Lisp goes beyond APL by also having mobile functions.  From a
programmer's viewpoint the main difference between an expression and a function
is that functions are objects that explicitly take arguments, whereas the only
way to pass information to an expression is to store it, before evaluating the
expression, in variables that the expression "knows" about.

	Lisp implements mobile functions by using lambda-expressions, a method
of representing functions due to the logician Alonzo Church.  For example, the
function that computes the length of a two-dimensional vector whose coordinates
are x and y could be represented with the list

	(Lambda (x y) (Sqrt (Plus (Times x x)
				  (Times y y))))

	Such an object can be read, printed, assigned to variables, passed as
an argument to another function, returned as the result of a function, and of
course applied to a pair of arguments.  To take an unusual example, running the
program (Apply (Read) (List 3 4)) would cause the function typed in response to
the Read to be applied to the list of arguments (3 4).  If the user typed in
the above lambda-expression, the result would be 5.

	The closest APL can come to this is to have a name of a function, say
ZOT, be a datum.  To apply the function so named in APL one would concatenate
the name with the argument(s), say 3, then Execute the resulting program "ZOT
3".  The catch is that names on their own mean nothing; the technique will not
work if the name is not defined, or if somebody changes its definition.  Thus
if you print the name of an APL function on a device from which you want to
read it back in later, the original definition may in the meantime change or
disappear from the workspace.  This difficulty does not arise with lambda
expressions, which contain their own definition.  Thus functions have at best
limited mobility in APL.

	The concept of mobility was first identified by Robin Popplestone in
1968 in describing the virtues of his language POP-2.  In hindsight it is clear
that this was a concern, whether or not a subconscious one, for the designers
of Lisp, APL and Snobol.  Popplestone used the term "first-class citizen" to
refer to a mobile datum.  I prefer "mobile" as being less of a mouthful.

2.  Modularity of function

	Subroutine libraries have something that programming languages often
lack, and that is modularity of function.  One does not view a subroutine
library as a monolith but rather as a loosely coupled set of subroutines.  The
term "subset," often applied in a vague way to programming languages, has an
obvious and precise meaning for subroutine libraries.

	Lisp and APL in contrast are each just like a subroutine library, being
little more than a set of functions.  The user may add to this set by getting
more functions from whatever subroutine library is maintained by the local
environment.  And the user's program itself consists of a set of functions.
Any of these functions can be invoked from the user's terminal or from the
user's or any other program.  All three kinds are invoked with identical
syntax: in Lisp,

	(Function Arg1 Arg2 ... Argn),

in APL

	op x	for unary functions
	x op y	for binary functions, assuming right associativity.

	The conventions for representing lists, Lisp's primary structured data
type, are the same for representing programs, and since those conventions are
simple there is little to learn.  In this respect Lisp differs from APL, which
has a convention for representing the structure of its programs (namely the
invocation of the right-associativity rule, that x op y op z is read as
x op (y op z)) that has no analog in the representation of APL data.

	I should add that my own preference in programming in Lisp is to use an
Algol-like language, Cgol, which is then automatically translated to Lisp.
Despite the regular and easily learned syntax of Lisp, I do not like having to
write x+y as (Plus x y).  I do too much mathematics to feel comfortable
switching representations in order to program.  Fortunately it is not necessary
to compromise functional modularity in order to use other syntactic
conventions.  If I were an APL programmer I would want to do the same thing:
have a syntactic preprocessor that permitted me to use the syntax I felt most
comfortable with.

3.  Declarative Programming

	Here is an innocent looking pair of equations.

		(a+1) x b  =  a x b + b
		    0 x b  =  0

	What sets these equations apart from the millions of other equations I
could have written is that these permit me to convert any method for adding
into a method for multiplying non-negative integers.  Suppose for example I
want to multiply 3 by 7.  Since 3 = 2+1 I can use the equation to express 3x7
as 2x7+7, reducing the original problem to a smaller one which can be solved by
the same method.  Eventually I have (((0x7+7)+7)+7), which the second equation
turns into (((0+7)+7)+7).  Using the method for adding, three times, I end up
with the desired answer.

	Turning these equations into a Lisp program to give a recursive
definition of (Times a b) is an essentially mechanical procedure yielding

	(Cond ((Zerop a) 0)
	      (T (Plus (Times (Sub1 a) b) b)))

or in the "syntactically sugared" version of Lisp referred to earlier,

	if a=0 then 0 else (a-1)*b+b.

	The significance of this example lies in the observations that (i) the
facts were so obvious it was hard to make a mistake, and (ii) the procedure for
converting those facts into something we could run as a program was so
stereotyped and straightforward (match the problem against the left hand side
of an equation, replace it by the corresponding right hand side) that again it
was hard to make a mistake.

	Programming in Lisp comes close enough to this "declarative" style to
make programming a remarkably error-free process.  A well-written Lisp program
will look (to those who can read Lisp) like a collection of facts.  The
subtlety of the program then amounts to the subtlety of the facts.  If the
facts are obvious, as with the above, there is little to explain.  If the facts
are obscure then you have a program that needs to be proved correct.

	Though the example above dealt with numbers, the mobility of Lisp's
structured data types makes it possible to apply the same method to writing
programs that operate on lists, functions, programs, and so on.

	My own research includes developing and testing new algorithms for a
variety of problems.  For the sake of ease of implementation and short
debugging time, my style is, as far as possible, to set down the facts relevant
to the computation and express them as Lisp functions.  Thanks to the quality
of the Lisp compiler used at MIT I end up with reasonably efficient programs,
in many cases as efficient as if I had adopted a more traditional style of
programming with while loops and assignments.  (One thing I miss, however, is
the ability to just write down the pure equations and have a preprocessor
automatically combine them into a single Lisp program.)

	My prime testing program referred to in Martin Gardner's Scientific
American column for August 1978 is written entirely in this style.  Some of the
facts it uses are obvious ones concerning such topics as exponentiation modulo
n.  Some of the facts however are considerably deeper and were first proved by
the well-known computer scientist Michael Rabin.

	Rewriting this particular program in some other programming style would
achieve little if anything in the way of efficiency.  It would however make it
harder to see the connection between the collection of facts supporting the
method and the program itself.  Rewriting the program in another programming
language while preserving the declarative style would be possible provided
recursion was permitted and numbers were mobile.  (A catch here is that numbers
of the size my program works with, up to a thousand decimal digits, are not
merely not mobile in most languages, they do not even exist.  The implementation
at MIT is one of the implementations which take pains to protect the programmer
from too frequent painful encounters with boundaries by not limiting the size
of integers.)

	This principle of executing facts as programs has encouraged people to
generalize the idea to other facts besides equations, and a series of
programming languages have evolved based on this generalization, two of the
more prominent ones being Planner and Prolog.

4.  Metalanguage

"Meta" is Greek for "about."  Lisp lists can be used, inter alia, to represent
expressions in various languages.  Thus Lisp makes an ideal metalanguage, a
language for talking about language.  As such Lisp finds application in a large
variety of areas dealing with the processing of language, as shown in the
table.

	Area			   Language
  Compiling			Parsed programs
  Algebraic Simplification	Algebraic formulas
  Natural Language		Parsed sentences
  Automatic Theorem Proving	Logical formulas
  Program Verification		Parsed programs and logical formulas
  Automatic Programming		Specifications and resulting programs
  Knowledge-Based Systems	Facts and rules

	In all of these areas, the expressions of the language in question are
treated as structures rather than as strings.  Structures represent the level
of language processing where the real action is.  Parsing (converting strings
to structures) may present more or less of a challenge depending on the area,
but the general feeling in most such areas is that it is what takes place after
parsing that is more interesting.

	What makes Lisp particularly well suited to these applications is that
they frequently call for operations on expressions that are best viewed
recursively as facts and procedures stated in terms of the immediate
constituents of the expressions.  This is an instance of the declarative style
described earlier, for the case when the data are expressions.

	To take an example from algebraic simplification, the derivative of an
expression can be defined in terms of the derivatives of its immediate
constituents.  Thus (Deriv '(Plus x y)) would be

	(List 'Plus (Deriv x)
		    (Deriv y))

where x and y themselves may be quite complicated algebraic expressions.
Similarly (Deriv '(Times x y)) would be

	(List 'Plus (List 'Times (Deriv x) y)
		    (List 'Times x (Deriv y)))

and so on for other operators.  From such facts it is straightforward to
construct a recursive Lisp program for differentiating algebraic expressions.

	A helpful way to think about the principle illustrated by the above is
to view the equations from which the Lisp programs are derived as dealing with
only a small region of an expression at a time.  While algebra tends to supply
particularly nice examples of this principle, the principle in one form or
another pervades essentially all areas where linguistic structures are
encountered.

Conclusion

	This discussion of Lisp has confined itself to those aspects of Lisp
directly visible to the user.  It has not considered Lisp's substantial
contributions to language implementation technology, such as garbage
collection, the interpreter/compiler dichotomy, and dynamic module linking in
place of the usually more static linking loader.  It did consider Lisp's
relation to other languages, finding APL to be as good as Lisp in some
respects, but lacking in some particularly vital areas.

	While it is difficult to consider Lisp unique in any single one of its
aspects, when looked at as a whole Lisp stands out as a quite remarkable and
original language that does credit to its inventor, John McCarthy.


****************************************************************************************
Biographical Sketch for Vaughan Pratt

(Is this what you meant?  I couldn't find any biographical sketches in past
copies of Byte to model this on.)

Left Australia 1969
Ph.D. under Knuth at Stanford ("Shell Sort and Sorting Networks")
Joined MIT faculty 1972, Dept. of Electrical Engineering and Computer Science
Associated with Lab. for Computer Science, and Artificial Intelligence Lab.
Currently Head of Theory of Computation in LCS
Worked in Natural Language, Algorithms, Program Semantics, Verification
Hobbies: Collecting/repairing/playing musical instruments, building robots